namespace Gauss_det {
	static const int N = 105;
	int A[N][N];
	int gauss(int n) {
		int x = 1;
		for (int i = 0; i < n; i++) {
			if(!A[i][i]) {
				int j;
				for (j = i + 1; j < n; j++)
					if (A[j][i]) break;
				if (j == n) return 0;
				for (int k = i; k < n; k++)
					swap(A[i][k], A[j][k]);
				x = 1LL * x * (MOD - 1) % MOD;
			}
			x = 1LL * x * A[i][i] % MOD;
			int sb = pow_mod(A[i][i], MOD - 2);
			for(int k = i + 1; k < n; k++)
				A[i][k] = 1LL * A[i][k] * sb % MOD;
			for(int j = i + 1; j < n; j++)
				for (int k = i + 1; k < n; k++)
					A[j][k] = (A[j][k] - 1LL * A[j][i] * A[i][k] % MOD + MOD) % MOD;
		}
		return x;
	}
}
